A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

Automatic 3d free form shape matching using the graduated assignment algorithm

Three-dimensional free form shape matching is a fundamental problem in both the machine vision and pattern recognition literatures. However, the automatic approach to 3D free form shape matching still remains open. In this paper, we propose using k closest points in the second view for the automatic 3D free form shape matching. For the sake of computational efficiency, the optimised k-D tree is employed for the search of the k closest points. Since occlusion and appearance and disappearance of points almost always occur, slack variables have to be employed, explicitly modelling outliers in the process of matching. Then the relative quality of each possible point match is estimated using the graduated assignment algorithm, leading the camera motion parameters to be estimated by the quaternion method in the weighted least-squares sense. The experimental results based on both synthetic data and real images without any pre-processing show the effectiveness and efficiency of the proposed algorithm for the automatic matching of overlapping 3D free form shapes with either sparse or dense points.     

Switching class labels to generate classification ensembles

Ensembles that combine the decisions of classifiers generated by using perturbed versions of the training set where the classes of the training examples are randomly switched can produce a significant error reduction, provided that large numbers of units and high class switching rates are used. The classifiers generated by this procedure have statistically uncorrelated errors in the training set. Hence, the ensembles they form exhibit a similar dependence of the training error on ensemble size, independently of the classification problem. In particular, for binary classification problems, the classification performance of the ensemble on the training data can be analysed in terms of a Bernoulli process. Experiments on several UCI datasets demonstrate the improvements in classification accuracy that can be obtained using these class-switching ensembles.     

特征选择算法在故障检测中的应用研究

将基于决策树的特征选择方法应用于卫星故障检测中,在卫星故障检测应用研究中,综合分析了问题的特征,指出了基于决策树的特征选择方法,并且给出了在该方法下,特征选择算法的正确率和在卫星故障检测中的应用效果。     

具有多等位环的高压屏蔽新结构MER-LDMOS耐压分析

提出一种多等位环(multiple equipotential rings,MER)的高压屏蔽新结构MER-LDMOS,并解释了该结构的屏蔽机理,通过2D器件模拟验证了屏蔽机理的正确性.讨论了p-top剂量、等位环长度、等位环间距以及氧化层厚度对MER-LDMOS击穿电压的影响.结果表明MER-LDMOS突破常规LDMOS高压屏蔽的能力,击穿电压较常规LDMOS提高一倍以上;同时,该结构具有工艺简单、工艺容差大、反向泄漏电流小等优点,为高压集成电路中高压屏蔽的问题提供了一种新的解决方案.     

基于攻击树的协同入侵攻击建模

由于现代入侵方法从单步入侵转变到协同入侵,文章在传统攻击树基础上,提出了分层次攻击树,并用模块化的方法为协同攻击建模,以IP-spoofing攻击为例说明了建模方法。     

基于DCT系数小波重组的图像压缩算法

论文提出一种与小波变换结构近似的嵌入式编码—MSESPIHT。将图像8×8子块进行DCT变换后的系数按照小波变换结构重新组合,运用均值去除法降低低频段系数的冗余度。之后,运用基于分层树集合分割排序的编码算法对图像进行压缩编码。实验表明,采用MSESPIHT处理的图像,在相同压缩比的情况下,图像质量得到改善,当码率为1.00bpp时,EZW、MSEDCT、SPIHT、MSESPIHT、峰值信噪比分别为39.55dB、39.75dB、39.97dB、40.12dB。     

交联聚乙烯电缆中电树枝的研究现状

总结了电树枝研究的最新进展,特别是交联聚乙烯电缆绝缘中电树枝的研究现状。对电树枝的分类以及在电树枝引发和生长过程中的一些影响因素进行了讨论。最后从实际应用出发,简要介绍了交联聚乙烯电缆中电树枝的诊断方法。     

A suffix tree approach to anti-spam email filtering

We present an approach to email filtering based on the suffix tree data structure. A method for the scoring of emails using the suffix tree is developed and a number of scoring and score normalisation functions are tested. Our results show that the character level representation of emails and classes facilitated by the suffix tree can significantly improve classification accuracy when compared with the currently popular methods, such as naive Bayes. We believe the method can be extended to the classification of documents in other domains. Editor: Tom Fawcett     

The reliability of general vague fault-tree analysis on weapon systems fault diagnosis

An algorithm of vague fault-tree analysis is proposed in this paper to calculate fault interval of system components from integrating expert's knowledge and experience in terms of providing the possibility of failure of bottom events. We also modify Tanaka et al's definition and extend the new usage on vague fault-tree analysis in terms of finding most important basic system component for managerial decision-making. In numerical verification, the fault of automatic gun is presented as a numerical example. For advanced experiment, a fault tree for the reactor protective system is adopted as simulation example and we compare the results with other methods. This paper also develops vague fault tree decision support systems (VFTDSS) to generate fault-tree, fault-tree nodes, then directly compute the vague fault-tree interval, traditional reliability, and vague reliability interval.